/**
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：

输入：s = "cbbd"
输出："bb"
 */
//动态规划
var longestPalindrome = function(s) {
  const m = s.length;
  let start = 0;
  let end = 0;
  const dp = Array(m).fill().map(() => Array(m).fill(false));
  for(let i=0;i<m;i++) {
    dp[i][i] = true;
  }
  // 保证 i～j中间已经计算过
  for(let i = m-1; i>=0;i--) { //倒叙遍历
    for(let j=i+1; j<m;j++) { // 从当前指针往前遍历
      if(s[i]==s[j] && (dp[i+1][j-1] || j-i<2)){
        dp[i][j] = true;
        if(j-i>end-start){
          start = i;
          end = j;
        }
      }
    }
  }
  return s.slice(start,end+1);
};
console.log(longestPalindrome("a")) //"a"
console.log(longestPalindrome("babad")) //"bab"
console.log(longestPalindrome("cbbd")) //"bb"